//输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 
//
// 
//
// 示例 1: 
//
// 输入: [10,2]
//输出: "102" 
//
// 示例 2: 
//
// 输入: [3,30,34,5,9]
//输出: "3033459" 
//
// 
//
// 提示: 
//
// 
// 0 < nums.length <= 100 
// 
//
// 说明: 
//
// 
// 输出结果可能非常大，所以你需要返回一个字符串而不是整数 
// 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 
// 
// Related Topics 排序 
// 👍 59 👎 0

package leetcode.editor.cn;
//Java：把数组排成最小的数
public class BaShuZuPaiChengZuiXiaoDeShuLcof{
    public static void main(String[] args) {
        Solution solution = new BaShuZuPaiChengZuiXiaoDeShuLcof().new Solution();
        System.out.println(solution.minNumber(new int[]{3,30,34,5,9}));
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String minNumber(int[] nums) {
        //将数组按照前几位数进行排序
        if(nums==null||nums.length<=0){
            return null;
        }
        int len=nums.length;
        int begin=0,end=len-1;
        StringBuilder sb=new StringBuilder();
        String[] strs=new String[len];
        for(int i=0;i<len;i++){
            strs[i]=""+nums[i];
        }
        quickSort(strs,begin,end,len);

        for(String str:strs){
            sb.append(str);
        }
        return  sb.toString();
    }

    //尝试使用快排来实现这道题目
    public void quickSort(String[] strs,int begin,int end,int len){
        if(begin<0||begin>=len||end<0||end>=len){
            return;
        }
        if(begin>=end){
            return;
        }

        //index已经在它的位置上了
        int index=partition(strs,begin,end,len);
        if(index>begin){
            quickSort(strs,begin,index-1,len);
        }
        if(index<end){
            quickSort(strs,index+1,end,len);
        }
    }

    public  int partition(String[] strs,int begin,int end,int len){
        if(begin<0||begin>=len||end<0||end>=len||begin>=end){
            return -1;
        }

        int index=begin+(int)(Math.random()*(end-begin+1));
        int small=begin-1;//记录已经交换过的范围
        swap(strs,index,end);

        for(int i=begin;i<=end;i++){
            if(compare(strs[i],strs[end])<0){
                small++;
                if(small!=i){
                    swap(strs,small,i);
                }
            }
        }
        small++;
        swap(strs,small,end);
        return  small;
    }

    public int compare(String s1,String s2){
        return (s1+s2).compareTo(s2+s1);
    }
    public void swap(String[] strs,int i,int j){
        String tmp=strs[i];
        strs[i]=strs[j];
        strs[j]=tmp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
